一个关于并查集的问题

首先，其实我去年就在讨论区问过这个问题的，但是……没人理我……

就是这么个东西，一个普通的，带路径压缩的并查集

int n, f[N], counter = 0;
int fa(int x) {
	counter++;
	return f[x] == x ? x : f[x] = fa(f[x]); 
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i < n; i++) {
		f[i] = f[i-1] = i;
		fa(rand() % i);
	}
	printf("%d\n", counter);
}

其中rand()返回的是均匀随机数，求输出的counter的数学期望

根据一波打表找规律发现答案是

$n\sum_{i=1}^{n-1}\frac{1}{i}$

证明：

定义合法树为：每个节点的编号均小于其父节点编号的树，那么：

1. 对于每个随机序列，按照以上代码生成的树都是合法树
2. 不同的随机序列有$(n-1)!$种
3. 不同的合法树有$(n-1)!$种
4. 对于每个合法树，都存在一个随机序列，使得按照以上代码能生成该树

简述下第四条的构造方法，对于一棵合法树，每次删除根节点，则剩下的子树里编号最小的点就是序列的最后一个点。把剩下的子树按照节点编号大小排序连成一条链，那么对该树上刚才找到的点进行路径压缩可以得到原树（如下图），且显然这样做剩下的树仍然是合法树，循环下去求即可

结合以上四条，可得：随机序列和合法树是一一对应的

那么我们要求的就是所有合法树上平均的答案，很容易递推

设$f(n)$为counter的期望，$h(n)$为点数为$n$的合法树所有节点深度的平均值（根节点深度为$1$），则有递推式

$f(1)=0$

$h(1)=1$

$f(n)=1+f(n-1)+h(n-1)$

$h(n)=h(n-1)+\frac{1}{n}$

然后随便推两下就能求出来了

证毕